1. Field of the Invention
The invention generally concerns generating an output stream with real-time properties from a representation of the output stream that specifies the real-time properties of the output stream. More particularly, the invention concerns techniques for reducing the delay in beginning to generate the output stream from the representation when the representation is not monotonic with regard to time. The techniques are particularly useful in generating a stream of MIDI events from a MIDI file before the entire MIDI file has been received in the device that is generating the stream of events.
2. Description of the Prior Art
The Musical Instrument Digital Interface (MIDI) is a standard protocol for controlling electronic musical instruments such as synthesizers or the sound cards of personal computers. One common use of the protocol is permitting a musician to play more than one electronic instrument at once. The instrument that the musician is actually playing not only generates sounds, but also generates a sequence of event messages. An event message may for example be a note on message, that indicates that a note of a given pitch has started to sound or a note off message that indicates that the note has ceased sounding. Many other kinds of event messages are defined as well. Another instrument receives the event messages from the first instrument and responds by performing the actions indicated in the messages. Thus, if the message is a note on message, the other instrument will begin sounding the note, and will thus "play along with" the first instrument. For purposes of the present discussion, the event messages can be divided into two classes: the note on and note off messages and the remaining messages, which will be termed herein control messages.
The sequence of MIDI protocols to which a musical instrument directly responds is termed herein a MIDI stream. Devices which respond to a MIDI stream are termed herein MIDI devices. In a MIDI stream, time relationships between events are simply determined by when the events appear in the event stream. For example, if a note is to be held for a period of one second, the note on message for the note will appear in the MIDI stream one second before the note off message for the note appears in the stream. Since the MIDI device will start sounding the note in response to the note on message and stop sounding the note in response to the note off message, the note will be sounded for one second.
A MIDI stream may be produced not only by an electronic musical instrument, but also from a MIDI file. The MIDI file is stored in memory and is then read by a device called a MIDI controller to generate a MIDI stream. This process of reading a MIDI file and generating a MIDI stream from it is termed herein playing the MIDI file. A MIDI file is made up of a sequence of MIDI event messages separated by elapsed time descriptors. An elapsed time descriptor specifies the time that is to elapse between the time the MIDI controller places the MIDI event message that precedes the elapsed time descriptor in the MIDI stream and the time that the controller places the event message that follows the elapsed time descriptor in the MIDI stream. There are at present two standard formats for MIDI files. In one format, known as Format 0, the file is simply a single sequence of event messages and elapsed time descriptors. In the following, such a sequence of event messages and elapsed time descriptors will be termed a track. In the other format, known as Format 1, the file has a number of tracks. Each track corresponds roughly to a part in a piece of ensemble music. In the case of Format 0, the MIDI controller generates the MIDI stream from the file by outputting a given event message, waiting the time specified in the elapsed time descriptor, and outputting the next event message. In the case of Format 1, the MIDI controller generates the MIDI stream by reading the tracks "simultaneously", that is, by outputting the event messages in each track that correspond to a given point in time in the music to the MIDI stream at that point in time. Most MIDI files are format 1 files, since the use of tracks makes it easy to modify a part or add a part. The standards for both MIDI streams and MIDI files are defined in the MIDI Specification, copyright 1983 and available from the MIDI Manufacturers' Association.
FIG. 1 shows a prior-art arrangement 101 for generating a MIDI stream from a MIDI format 1 file 103. Midi file 103 has a header 104 which contains information such as the number of tracks. The MIDI file also contains at least one track 105. A given track i in such a file is indicated hereinafter by 105(i). Each track 105(i) contains a sequence of events 106. Each event 106(j) has two parts: an event message 117 and an elapsed time descriptor 119. The elapsed time descriptor indicates the time that is to elapse between the preceding event 106(j-1) and event 106(j). As can be seen from the foregoing, a given event 106's position in file 103 may be indicated by the index of its track and its own index in the track. Event 106(i,j) is thus event j in track i.
The MIDI stream 111 is generated from MIDI file 103 by MIDI controller 107. Prior-art MIDI controller 107 does this by first writing all of the tracks 105 from file 103 into controller memory 109, as shown by arrow 108, and then reading all of the tracks simultaneously in the fashion just described, as shown by arrow 110. To accomplish the simultaneous reading, MIDI controller 107 maintains a song position time value 121 which the controller can use together with the elapsed time descriptors to determine which event messages are to be output from the tracks at a given time. As would be expected from this procedure, and as shown in FIG. 1, MIDI stream 111 generally consists of interleaved event messages 117 from the tracks 105. MIDI stream 111 may then be responded to by any MIDI device 113, which then drives loudspeaker 115 to produce the sounds specified by MIDI stream 111.
While the MIDI protocol was originally developed for electronic instruments, it is being increasingly used in computer systems. In such systems, the MIDI files are stored at a location accessible to the computer system, the MIDI controller is a program which executes in the computer system, and the MIDI device to which the MIDI controller outputs the MIDI stream is a sound board in the computer system. Even more recently, MIDI files have been included as part of World Wide Web pages that may be accessed via the Internet. The Web browsers that are used to view such pages include programs that work as MIDI controllers to play the MIDI file included in the Web page as the Web page is being viewed. The included MIDI file can thus be used to provide background music for the Web page. When a user has a Web browser that can play a MIDI file, the user can also select a link to a MIDI file from a Web page and hear the music that the MIDI file represents. An example of a Web browser that can play a MIDI file is the well-known Netscape browser with the Crescendo plug-in produced by Laboratories Technologies Corporation, 400 Research Drive, Wilmington, Mass. 01887. Netscape and Crescendo are trademarks of Netscape Communications Corporation and Laboratories Technologies Corporation, respectively.
A problem with prior-art MIDI controllers 107 is that controller 107 must load all of the tracks from MIDI file 103 being played into controller memory 109 before MIDI controller 107 can start playing MIDI file 103. Consequently, there will always be some delay between the time that controller 107 is commanded to start playing MIDI file 103 and the time that MIDI device 113 actually begins to output music. The length of the delay will of course depend on the size of file 103 and the bandwidth of the connection upon which MIDI controller 107 is receiving file 103. There are many cases in which the delay will be non-trivial, first, because the files may be very large (300 Kilobyte files with 35 tracks are not unknown) and second, because the files are often transferred via low-bandwidth connections. The latter situation is indeed generally the case when a MIDI file is being transferred via the Internet. While the MIDI file is being received and the tracks loaded into memory, there is nothing for the user to do but wait. This is of course particularly annoying when the MIDI file was intended to be background music for a Web page that must be displayed without music until the MIDI file is loaded.
The delay problem just described with regard to MIDI files exists wherever an output stream with real-time properties must be output from a representation in which the representation of the output stream is not monotonic with regard to time. One situation where this can occur with even a single track is if the material in the track is not in the order in which it is to be played. Another is where the representation of the output stream includes a plurality of segments that are read together to generate the output stream.
It is thus an object of the invention to provide methods and apparatus for overcoming the problems of delay that arise when an output stream with real-time properties is generated from a representation of the output stream which is not monotonic with regard to time.